package hot100.普通数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 *
 * @ https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked
 * @date 2025/08/26
 */
public class 合并区间_56 {

    public static void main(String[] args) {

    }

    /**
     * 排序+遍历维护最大值
     */
    public int[][] merge(int[][] intervals) {

        List<int[]> list = new ArrayList<>();
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        int left = 0, preMax;
        while (left < intervals.length) {
            preMax = intervals[left][1];
            int right = left + 1;
            while (right < intervals.length && intervals[right][0] <= preMax) {
                preMax = Math.max(preMax, intervals[right][1]);
                right++;
            }
            list.add(new int[]{intervals[left][0], preMax});

            left = right;
        }

        int[][] ans = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }

        return ans;
    }

}
